package com.neusoft.search.fibonacci;

import java.util.Arrays;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 斐波那契查找: 在二分查找的基础上，通过黄金分割点0.618进行优化（计算middle的公式优化）
 * @Desc TODO 完全搞不懂在干嘛
 * @Date 2024-12-08
 */
public class FibonacciSearch {

    /**
     * 斐波那契数组的长度
     */
    public static int FIBONACCI_ARR_SIZE = 20;

    /**
     * 斐波那契查找: mid=leftIndex+fibonacciArr(fibonacciIndex-1)-1
     *
     * @param arr    目标数组
     * @param target 目标元素
     * @return 返回找到的数据所在arr数组的索引；未找到返回-1
     */
    public static int fibonacciSearch(int[] arr, int target) {
        int leftIndex = 0;
        int rightIndex = arr.length - 1;
        int middleIndex = 0;
        // 斐波那契分割数值的下标
        int fibonacciIndex = 0;
        // 初始化一个斐波那契数组
        int[] fibonacciArr = initFibonacciArr(FIBONACCI_ARR_SIZE);

        // 获取斐波那契分割数值的下标
        while (rightIndex > fibonacciArr[fibonacciIndex] - 1) {
            fibonacciIndex++;
        }

        // fibonacciIndex[fibonacciIndex]值可能大于arr的长度，因此我们需要构造一个新的数组，并指向tempArr[],不足的部分会使用0填充
        int[] tempArr = Arrays.copyOf(arr, fibonacciArr[fibonacciIndex]);

        //举例: temp = {1,8, 10, 89, 1000, 1234, 0, 0}  => {1,8, 10, 89, 1000, 1234, 1234, 1234}
        for (int i = rightIndex + 1; i < tempArr.length; i++) {
            tempArr[i] = arr[rightIndex];
        }

        while (leftIndex <= rightIndex) {
            middleIndex = leftIndex + fibonacciArr[fibonacciIndex - 1] - 1;
            if (target < tempArr[middleIndex]) {
                rightIndex = middleIndex - 1;
                fibonacciIndex--;
            } else if (target > tempArr[middleIndex]) {
                leftIndex = middleIndex + 1;
                fibonacciIndex -= 2;
            } else {
                return Math.min(middleIndex, rightIndex);
            }
        }

        return -1;
    }

    /**
     * 初始化一个斐波纳契数组
     *
     * @return 斐波纳契数组
     */
    public static int[] initFibonacciArr(int fibonacciArrSize) {
        int[] fibonacciArr = new int[fibonacciArrSize];
        fibonacciArr[0] = 1;
        fibonacciArr[1] = 1;
        for (int i = 2; i < fibonacciArrSize; i++) {
            fibonacciArr[i] = fibonacciArr[i - 1] + fibonacciArr[i - 2];
        }

        return fibonacciArr;
    }
}
